function ArrayList() {

    this.array = [];

    ArrayList.prototype.insert = function (item) {
        this.array.push(item);
    }

    ArrayList.prototype.toString = function () {
        return this.array.join();
    }

    // 冒泡排序
    ArrayList.prototype.bubbleSort = function () {

        for (var i = 0; i < this.array.length - 1; i++) {
            for (var j = i + 1; j < this.array.length; j++) {
                // 找到最小的放在最前面
                if (this.array[i] > this.array[j]) {
                    this.swap(i, j);
                }
            }
        }
        return this.array;
    }

    ArrayList.prototype.swap = function (m, n) {
        var temp = this.array[m];
        this.array[m] = this.array[n];
        this.array[n] = temp;
    }


    // 选择排序
    ArrayList.prototype.selectionSort = function () {
        
        for (var i = 0; i < this.array.length - 1; i++) {
            var index = i;
            for (var j = i + 1; j < this.array.length; j++) {
                if (this.array[index] > this.array[j]) {
                    index = j;
                }
            }
            this.swap(i, index);
        }
        return this.array;
    }


    // 插入排序
    ArrayList.prototype.insertionSort = function () {

        for (var i = 1; i < this.array.length; i++) {
            var temp = this.array[i];
            var j = i;

            while (temp < this.array[j - 1] && j > 0) {
                this.array[j] = this.array[j - 1];
                j--;
            }
            this.array[j] = temp;
        }
        return this.array;
    }

    // 希尔排序 希尔排序就是插入排序的改进版，理解了插入排序就理解了希尔排序
    ArrayList.prototype.shellSort = function () {

        // 初始化的增量gap
        var gap = Math.floor(this.array.length / 2);

        // while循环(gap不断减小)
        while (gap >= 1) {
            // 以gap作为间隙，进行分组
            for (var i = gap; i < this.array.length; i++) {
                var temp = this.array[i];
                var j = i;
                while (temp < this.array[j - gap] && j >= gap) {
                    this.array[j] = this.array[j - gap];
                    j -= gap;
                }
                // 将j位置的元素赋值temp
                this.array[j] = temp;
            }

            gap = Math.floor(gap / 2);
        }

        return this.array
    }

    // 选择快排的枢纽
    ArrayList.prototype.median = function (left, right) {
        var center = Math.floor((left + right) / 2);

        if (this.array[left] > this.array[center]) {
            this.swap(left, center);
        }
        if (this.array[left] > this.array[right]) {
            this.swap(left, right);
        }
        if (this.array[center] > this.array[right]) {
            this.swap(center, right);
        }

        // 将center移动到 right - 1的位置
        this.swap(center, right - 1);

        // 返回枢纽
        return this.array[right - 1];
    }

    // 给外界调用的接口
    ArrayList.prototype.quickSort = function () {
        this.quick(0, this.array.length - 1);
        return this.array;
    }

    // 内部递归调用的方法
    ArrayList.prototype.quick = function (left, right) {

        // 递归结束的条件
        if (left >= right) {
            return
        }
        // 获取枢纽
        var pivot = this.median(left, right);
        // 设置两个指针指向最开始和枢纽
        var i = left;
        var j = right - 1;
        while (i < j) {
            // 从左找，找到比枢纽大的
            while (this.array[++i] < pivot) { // 因为找枢纽时，left已经是比枢纽小的了
            }
            // 从右找，找到比枢纽小的
            while (this.array[--j] > pivot) { // j = right - 1 就是枢纽本身，所以先--
            }
            // 进行交换,先进行判断
            if (i < j) {
                this.swap(i, j);
            }
            
        }
        // 循环结束后，应该是左边的都比枢纽小，右边的都比枢纽大
        // 将枢纽放置在 i > j时结束循环的位置
        this.swap(i, right - 1) // right - 1时枢纽此时的位置

        // 开始递归调用枢纽左边的一大块数值和枢纽右边的一大块数值
        this.quick(left, i - 1);
        this.quick(i + 1, right);
    }
}